基础背包问题

Posted on | Post modified: | In |
Words count in article: 2.5k

背包问题

01背包

01背包主要解决的问题就是选or不选的情况。枚举选了当前物品后的状态转移，而选当前物品之前的状态可以通过减去当前体积得到。

01背包分为两种，一种是固定容量，求能得到的最大价值。一种是确定最小价值，求可能的方案数量。有些类似对偶问题。

1. 最大价值解

模板题

物品只能使用一次，每个物品有不同的价值和体积，如何在给定容量选取物品得到最大价值。

关键点：

  1. 状态如何定义
  2. 子问题确定
  3. 如何枚举

物品的最大价值是需要求的，最大价值与选取哪些物品有关，而物品有两种属性(体积、价值)。令总价值为状态的值，而背包的容量为状态变量，其含义为容量为v的背包的最大价值。因为需要枚举物品，因此增加一维表示物品。

那么其子问题就是在前面n-1个物品使用v个体积所能达到的最大价值。

枚举的时候需要枚举容量，当前物品若能放下，则其转移为：

  • 一维优化
1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];

for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j) {
        f[i][j] = f[i - 1][j]; // 新加入物品后他的最大价值至少是之前的最大价值
        if (j >= v[i]) {       // 如果当前物品的体积小于该状态的总体积（能放下）
            f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
}
  • 二维空间
1
2
3
4
5
6
7
8
for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];

for (int i = 1; i <= n; ++ i) {
    for (int j = m; j >= v[i]; -- j) { // 内循环中v[i]是固定的，且只用到上一层
    	f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}
cout << f[m] << endl;
分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

  • 关键点

首先需要根据题目推出 目标是求一个子序列满足 其和为总和的一半。那么这个问题可以看作体积与价值相同的背包问题，并且容量是总和的一半。体积与价值相同便限制了加入背包的数之和（体积用于限制和，价值用于接近和）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool canPartition(vector<int>& nums) {
    // 等和首先需要推出 目标为总和的一半，然后在数组中选数字看能否得到这个目标
    int n = nums.size();
    int sum = 0;
    for (int x : nums)  sum += x;
    if (sum % 2) return false;
    sum /= 2;

    vector<int> dp(sum + 1); 
    for (int i = 1; i < n; ++ i) {  // 枚举n个数,这儿没有枚举到最后一个数是因为如果有答案一定是需要分两组，而前n-1个数中必定有答案了
        for (int j = sum; j >= nums[i - 1]; -- j) {  // 将容量限制到sum来枚举，得到sum以内的所有可能
            if (sum == dp[sum]) return true;
            dp[j] = max(dp[j], dp[j - nums[i - 1]] + nums[i - 1]);
        }
    }
    return sum == dp[sum];
}
一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

即给出一些物品，它们包含一和零，给出1和0的容量m，n。求最多物品的数量。相比于模板01背包，多了一维容量。直接当成二维来做就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findMaxForm(vector<string>& strs, int m, int n) {
    // 给出了两个容量
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (const string& s : strs) {
        int cnt0 = 0, cnt1 = 0;
        for (const char c : s) {
            if (c == '0') ++ cnt0;
            else ++ cnt1;
        }

        for (int i = m; i >= cnt0; -- i) {
            for (int j = n; j >= cnt1; -- j) {
                dp[i][j] = max(dp[i][j], dp[i - cnt0][j - cnt1] + 1);
            }
        }
    }
    return dp[m][n];
}
最后一块石头的重量II

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

使得消除后的石头重量最小，实际上也就是将它们分为质量最相近的两份，那么与分割等和子集就差不多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lastStoneWeightII(vector<int>& stones) {
    int n = stones.size();
    int sum = 0, ord = 0;
    for (int x : stones) sum += x;
    if (sum % 2) ord = 1;
    int target = sum / 2;

    vector<int> dp(target + 1, 0);
    for (int i = 0; i < n; ++ i) {  // 必须遍历每一个石头
        for (int j = target; j >= stones[i]; -- j) {
            if (target == dp[target]) return ord;    // 小优化
            dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }
    return sum - 2 * dp[target];
}

2. 最优解的方案数

组合总和IV

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

题目即求和为target的子序列的方案数，做法就是枚举1到target之间的所有可能值，计算其方案数，当前的目标值的方案数 += 选择当前数 之前的状态方案数，类似记忆化搜索。

1
2
3
4
5
6
7
8
9
10
11
12
int combinationSum4(vector<int>& nums, int target) {
    int n = nums.size();
    vector<unsigned long long> dp(target + 1);
    dp[0] = 1; // 目标为0 的方案有1个
    for (int i = 1; i <= target; ++ i) { // 枚举容量
        for (int j = 0; j < n; ++ j) {
            if (i >= nums[j]) 
                dp[i] += dp[i - nums[j]];
        }
    }
    return dp[target];
}
目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

题目要求在数组中为一部分选择+，一部分选择 - ，那么每个物品有三种选择：1. 不选， 2. 选+ ，3. 选 - 。这样不好处理。将问题变换一下，令选择 + 的部分为a， 选择 - 的部分为 b，那么：

同时，若a确定，则b确定，因此可将目标设为求 a ，这样就转化为了分割等和子集。稍有区别的是它求的是方案数，但枚举方法是一样的，类似记忆化，需要用到上一个物品选择后的dp状态，因此内层容量倒序枚举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int findTargetSumWays(vector<int>& nums, int S) {
    int n = nums.size();
    long sum = 0;
    for (int x : nums) sum += x;
    long target = sum + S;
    if (target % 2 || sum < S) return 0;
    target /= 2;

    vector<unsigned long long> dp(target + 1);
    dp[0] = 1;
    for (int i = 0; i < n; ++ i) {
        for (int j = target; j >= nums[i]; -- j) {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[target];
}
盈利计划

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为盈利计划。并且工作的成员总数最多为 n 。

有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
    const long mod = 1e9 + 7;
    int n = profit.size();
    vector<vector<int>> dp(G + 1, vector<int>(P + 1));
    for (int i = 0; i <= G; ++ i) dp[i][0] = 1;     // 每个团队0利润的方案为1

    for (int i = 0; i < n; ++ i) {                  // 枚举n个团队
        int g = group[i], p = profit[i];

        for (int j = G; j >= g; -- j) {             // 枚举两个容量， 人数 和 收益
            for (int k = P; k >= 0; -- k) {         //
                dp[j][k] += dp[j - g][max(k - p, 0)];
                dp[j][k] %= mod;
            }
        }
    }
    return dp[G][P];
}

其他背包

完全背包

物品可无限使用

物品可选无限次，那么dp更新的时候公式就变化了

而注意到

可以看出二式相比于一式的后面只少了w，因此

完全背包与01背包公式不同的地方只是在更新的时候用的是本层的物品$i$，所以他们的枚举方式有细微区别，完全背包从前往后枚举即可。

对比01背包公式：

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];

for (int i = 1; i <= n; ++ i) {
    for (int j = v[i]; j <= m; ++ j) {  // 01 ： for (j = m; j >= v[i]; --j)
    	f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}
cout << f[m] << endl;

多重背包

物品限制了件数